/*

"unicode iterator". An on the fly codepoint conversion iterator compatible with STL.
Copyright (C) 2013 Owen Thirlwell

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

*/

#pragma once

#include <iterator>

namespace unicode
{
	typedef unsigned char utf8;
	typedef wchar_t utf16;
	typedef unsigned long utf32;
	
	template < size_t N > struct type_with_size;
	template <> struct type_with_size< 4 > { typedef utf32 value; };
	template <> struct type_with_size< 2 > { typedef utf16 value; };
	template <> struct type_with_size< 1 > { typedef utf8 value; };
	
	template< class T > struct iterator_for
	{
		typedef typename type_with_size< sizeof(T::value_type) >::value type;
		typedef typename T::const_iterator iterator;
	};
	template< class T > struct iterator_for< T* >
	{
		typedef typename type_with_size< sizeof(T) >::value type;
		typedef const T* iterator;
	};

	namespace constants
	{
		static const utf16 LeadingSurrogateLow = 0xd800u;
		static const utf16 LeadingSurrogateHigh  = 0xdbffu;
		static const utf16 TrailingSurrogateLow = 0xdc00u;
		static const utf16 TrailingSurrogateHigh = 0xdfffu;
		static const utf16 SurrogateOffset = LeadingSurrogateLow - (0x10000 >> 10);
		static const utf32 SurrogateDelta = 0x10000u - (LeadingSurrogateLow << 10) - TrailingSurrogateLow;
		static const utf16	ReplacementChar = 0xfffd;
		static const utf8	ReplacementChars[] = { 0xef, 0xbf, 0xed };
		static const utf32 MaxCodepoint = 0x0010ffffu;

		inline static bool isLeadingSurrogate ( utf32 _codepoint ) { return (_codepoint >= LeadingSurrogateLow && _codepoint <= LeadingSurrogateHigh); }
		inline static bool isTrailingSurrogate ( utf32 _codepoint ) { return (_codepoint >= TrailingSurrogateLow && _codepoint <= TrailingSurrogateHigh); }
		inline static bool isSurrogate ( utf32 _codepoint ) { return (_codepoint >= LeadingSurrogateLow && _codepoint <= TrailingSurrogateHigh); }
		inline static bool isValidCodepoint ( utf32 _codepoint ) { return (_codepoint <= MaxCodepoint); }
		inline static bool isSingleByte ( utf8 _codepoint ) { return ((_codepoint & 0x80) == 0); }
		inline static bool isLeadingByte ( utf8 _codepoint ) { return ((_codepoint - 0xc0) < 0x3e); }
		inline static bool isTrailingByte ( utf8 _codepoint ) { return ((_codepoint & 0xc0) == 0x80); }
	}

	/*
	*	Base class for all exceptions
	*	TODO, return the actual iterator
	*/
	class exception : public std::exception
	{
	};
	class invalid_code_point : public exception
	{
		utf32 _codepoint;
	public:
		invalid_code_point ( utf32 ch ) : _codepoint( ch ) {}
		virtual const char* what ( void ) const throw() { return "Invalid code point"; }
		utf32 code_point ( void ) const { return _codepoint; }
	};
	class invalid_utf8 : public exception
	{
		utf8 _codepoint;
	public:
		invalid_utf8 ( utf8 ch ) : _codepoint( ch ) {}
		virtual const char* what ( void ) const throw() { return "Invalid UTF-8"; }
		utf8 code_point ( void ) const { return _codepoint; }
	};
	class invalid_utf16 : public exception
	{
		utf16 _codepoint;
	public:
		invalid_utf16 ( utf16 ch ) : _codepoint( ch ) {}
		virtual const char* what ( void ) const throw() { return "Invalid UTF-16"; }
		utf16 code_point ( void ) const { return _codepoint; }
	};

	enum iterator_flags
	{
		useDefault = 0,
		useReplacementChar = 1,
		useExtendedUtf8 = 2,		// CESU-8
		useEncodedNull = 4
	};

	/*
	*	useReplacementChar will prevent exceptions being thrown.
	*	useExtendedUtf8 will allow utf8 encoding of a null code point
	*	useEncodedSurrogates will allow utf8 encoded surrogate pairs
	*/
	template < typename _Container, typename _Type, iterator_flags _Flags = useDefault >
	class iterator : public std::iterator< std::random_access_iterator_tag, typename const type_with_size< sizeof( _Type ) >::value >
	{
		typedef typename iterator_for< _Container >::type				_FromType;
		typedef typename iterator_for< _Container >::iterator			_Iterator;
		typedef typename type_with_size< sizeof( _Type ) >::value	_ToType;

		class Container
		{
			union {
				utf32 m_utf32[ 1 ];
				utf16 m_utf16[ 2 ];
				utf8 m_utf8[ 4 ];
			};
			difference_type m_nIndex;
			difference_type m_nLength;

		public:
			Container ( void ) : m_nIndex( 0 ), m_nLength( 0 ) {}

			void clear ( void ) { m_nIndex = 0; m_nLength = 0; }

			template < typename T > void set ( utf32 ) ;
			template <> void set< utf8 > ( utf32 _codepoint )
			{
				m_nIndex = 0;
				if ( _codepoint < 0x80 )
				{
					m_nLength = 1;
					m_utf8[ 0 ] = static_cast< utf8 >( _codepoint );
				}
				else if ( _codepoint < 0x800 )
				{
					m_nLength = 2;
					m_utf8[ 0 ] = static_cast< utf8 >((_codepoint >> 6) | 0xc0);
					m_utf8[ 1 ] = static_cast< utf8 >((_codepoint & 0x3f) | 0x80);
				}
				else if ( _codepoint < 0x10000 )
				{
					m_nLength = 3;
					m_utf8[ 0 ] = static_cast< utf8 >((_codepoint >> 12) | 0xe0);
					m_utf8[ 1 ] = static_cast< utf8 >(((_codepoint >> 6) & 0x3f) | 0x80);
					m_utf8[ 2 ] = static_cast< utf8 >((_codepoint & 0x3f) | 0x80);
				}
				else if ( _codepoint < 0x110000 )
				{
					m_nLength = 4;
					m_utf8[ 0 ] = static_cast< utf8 >((_codepoint >> 18) | 0xf0);
					m_utf8[ 1 ] = static_cast< utf8 >(((_codepoint >> 12) & 0x3f)| 0x80);
					m_utf8[ 2 ] = static_cast< utf8 >(((_codepoint >> 6) & 0x3f) | 0x80);
					m_utf8[ 3 ] = static_cast< utf8 >((_codepoint & 0x3f) | 0x80);
				}
				else
					throw invalid_code_point( _codepoint );
			}
			template <> void set< utf16 > ( utf32 _codepoint )
			{
				m_nIndex = 0;
				if ( _codepoint > 0xffff )
				{
					m_nLength = 2;
					m_utf16[ 0 ] = static_cast< utf16 >( (_codepoint >> 10) + constants::SurrogateOffset );
					m_utf16[ 1 ] = static_cast< utf16 >( (_codepoint & 0x3ff) + constants::TrailingSurrogateLow );
				}
				else
				{
					m_nLength = 1;
					m_utf16[ 0 ] = static_cast< utf16 >( _codepoint );
				}
			}
			template <> void set< utf32 > ( utf32 _codepoint )
			{
				m_nIndex = 0;
				m_nLength = 1;
				m_utf32[ 0 ] = _codepoint;
			}

			template < typename T > inline reference get ( void ) ;
			template <> inline reference get< utf32 > ( void )
			{
				return m_utf32[ m_nIndex ];
			}
			template <> inline reference get< utf16 > ( void )
			{
				return m_utf16[ m_nIndex ];
			}
			template <> inline reference get< utf8 > ( void )
			{
				return m_utf8[ m_nIndex ];
			}

			difference_type length ( void ) const { return m_nLength; }
			difference_type index ( void ) const { return m_nIndex; }

			difference_type remainder ( void ) const { return m_nLength > 0 ? m_nLength - std::min( m_nIndex, m_nLength ) : 0; }

			bool empty ( void ) const { return (m_nIndex >= m_nLength); }

			Container & operator ++ ( void )
			{
				++m_nIndex;
				return *this;
			}
			Container & operator -- ( void )
			{
				--m_nIndex;
				return *this;
			}

			bool operator == ( const Container & _other ) const
			{
				return (m_nIndex == _other.m_nIndex && m_nLength == _other.m_nLength);
			}
		};

		Container				m_Cache;
		_Iterator				m_Iter;
		
		/*
		*	Look only at the current value and determine the expected value count
		*/
		template < typename T > difference_type sequenceLength ( T ) const ;
		template <> inline difference_type sequenceLength< utf32 > ( utf32 _codepoint ) const
		{
			return 1;
		}
		template <> inline difference_type sequenceLength< utf16 > ( utf16 _codepoint ) const
		{
			if ( constants::isLeadingSurrogate( _codepoint ) )
				return 2;
			return 1;
		}
		template <> inline difference_type sequenceLength< utf8 > ( utf8 _codepoint ) const
		{
			if ( _codepoint < 0x80 )				return 1;
//			if ( (_codepoint >> 6) == 0x2 )		return 1; // <-- Single trailing byte
			if ( (_codepoint >> 5) == 0x6 )		return 2;
			if ( (_codepoint >> 4) == 0xe )		return 3;
			if ( (_codepoint >> 3) == 0x1e )		return 4;
//			if ( (_codepoint >> 2) == 0x3e )		return 5; // <-- 4 trailing bytes
//			if ( (_codepoint >> 1) == 0x7e )		return 6; // <-- 5 trailing bytes
			return 0;
		}

		/*
		*	Move the supplied iterator from beginning of current sequence to next.
		*	Iterator MUST be on a valid sequence boundary.
		*	By default, if current code point is invalid, it will skip it.
		*	Caller must validate next sequence.
		*/
		template < typename T > inline void nextCodepoint ( _Iterator & ) ;
		template <> inline void nextCodepoint< utf32 > ( _Iterator & _Iter )
		{
			++_Iter;
		}
		template <> inline void nextCodepoint< utf16 > ( _Iterator & _Iter )
		{
			if ( constants::isLeadingSurrogate( *_Iter ) )
			{
				++_Iter;
				if ( constants::isTrailingSurrogate( *_Iter ) )
					++_Iter;
			}
			else
				++_Iter;
		}
		template <> inline void nextCodepoint< utf8 > ( _Iterator & _Iter )
		{
			difference_type nCount = sequenceLength< utf8 >( *_Iter );
			++_Iter;

			// Detect any invalid trailing bytes
			for ( difference_type n = 1; n < nCount; ++n, ++_Iter )
				if ( ! constants::isTrailingByte( *_Iter ) )
					break;
		}
		
		/*
		*	Move the supplied iterator from beginning of current sequence to previous.
		*	Iterator MUST be on a valid sequence boundary.
		*	Caller must validate any sequence after the decreased iterator.
		*/
		template < typename T > inline void prevCodepoint ( _Iterator & ) ;
		template <> inline void prevCodepoint< utf32 > ( _Iterator & _Iter )
		{
			--_Iter;
		}
		template <> inline void prevCodepoint< utf16 > ( _Iterator & _Iter )
		{
			--_Iter;
			if ( constants::isTrailingSurrogate( *_Iter ) )
				--_Iter;
		}
		template <> inline void prevCodepoint< utf8 > ( _Iterator & _Iter )
		{
			while ( constants::isTrailingByte( *(--_Iter) ) ) ;
		}

		/*
		*	Convert current iterator position to utf32 and move iterator to next sequence.
		*	Full validation is applied and will throw on failure unless useReplacementChar
		*	is set. Iterator may be anywhere in the stream but will only succeed if before
		*	a valid sequence.
		*/
		template < typename T > utf32 toUtf32 ( void ) ;
		template <> utf32 toUtf32< utf32 > ( void )
		{
			utf32 nCodepoint = *m_Iter;
			if ( ! constants::isValidCodepoint( nCodepoint ) || constants::isSurrogate( nCodepoint ) )
			{
				if ( (_Flags & useReplacementChar) != 0 )
					nCodepoint = constants::ReplacementChar;
				else
					throw invalid_code_point( nCodepoint );
			}
			++m_Iter;
			return nCodepoint;
		}
		template <> utf32 toUtf32< utf16 > ( void )
		{
			_Iterator Iter = m_Iter;
			utf32 nCodepoint;

			if ( constants::isLeadingSurrogate( static_cast< utf16 >( nCodepoint = *Iter ) ) )
				if ( constants::isTrailingSurrogate( *(++Iter) ) )
					nCodepoint = (nCodepoint << 10) + *Iter + constants::SurrogateDelta;

			if ( ! constants::isValidCodepoint( nCodepoint ) || constants::isSurrogate( nCodepoint ) )
			{
				if ( (_Flags & useReplacementChar) != 0 )
					nCodepoint = constants::ReplacementChar;
				else
					throw invalid_code_point( nCodepoint );
			}

			m_Iter = ++Iter;
			return nCodepoint;
		}
		template <> utf32 toUtf32< utf8 > ( void )
		{
			// Detect too few trailing bytes
			// Detect too many trailing bytes
			// Detect encoded null character 0xc0 0x80 (special handling)
			// Detect encoded surrogates
			// Detect overlong sequences.
			// Detect impossible bytes 0xfe 0xff
			// Detect illegal code points 0xffff 0xfffe
			// Deal with extended utf8, (surrogates)

			_Iterator Iter = m_Iter;
			utf32 nCodepoint = static_cast< utf8 >( *Iter );

			if ( nCodepoint == 0xfe || nCodepoint == 0xff )
			{
				if ( (_Flags & useReplacementChar) != 0 )
				{
					++m_Iter;
					return constants::ReplacementChar;
				}
				throw invalid_code_point( nCodepoint );
			}

			if ( (_Flags & useEncodedNull) != 0 )
			{
				// Test for utf8 null character
				if ( nCodepoint == 0xc0 && *Iter == 0x80 )
				{
					m_Iter += 2;
					return 0;
				}
				throw invalid_code_point( nCodepoint );
			}
			
			difference_type nCount = sequenceLength< utf8 >( static_cast< utf8 >( nCodepoint ) );

			// Combine and check any trailing bytes
			if ( nCount > 1 )
			{
				// Mask the first byte
				nCodepoint &= ((1 << (7 - nCount)) - 1);
				for ( difference_type n = 1; n < nCount; ++n )
				{
					++Iter;
					if ( constants::isTrailingByte( *Iter ) ) // <-- will return false for 0xff and 0xfe
						nCodepoint = nCodepoint << 6 | (*Iter & 0x3f);
					else
					{
						// Missing trailing bytes
						nCodepoint = 0;
						break;
					}
				}
			}
			
			// Check for overlong
			switch ( nCount )
			{
			case 1:	if ( nCodepoint < 0x80 )		break;
			case 2:	if ( nCodepoint < 0x800 )		break;
			// 0xfffe and 0xfffe are invalid
			case 3:	if ( nCodepoint < 0xfffe )		break;
				// Overlong and invalid
			case 4:	if ( nCodepoint < 0x110000 )	break;
				// Byte is a lone trailing byte
			case 0:
				// Invalid length
			case 5:	case 6:
			default:
				nCodepoint = 0;
				break;
			}

			// Check for surrogates
			if ( constants::isSurrogate( nCodepoint ) )
			{
				if ( (_Flags & useExtendedUtf8) == 0 )
					nCodepoint = 0;
			}

			// Handle any error
			if ( ! nCodepoint )
			{
				if ( (_Flags & useReplacementChar) != 0 )
					nCodepoint = constants::ReplacementChar;
				else
					throw invalid_code_point( nCodepoint );
			}

			m_Iter = ++Iter;
			return nCodepoint;
		}
		
		/*
		*	Fill the cache from the current iterator position. Full checking is done and will
		*	throw on failure. If exception is throw, the iterator will not have changed.
		*	Iterator MUST be on a valid boundary.
		*/
		inline void fillCache ( void )
		{
			m_Cache.set< _ToType >( toUtf32< _FromType >() );
		}

		/*
		*	Move the iterator to preceding boundary if not on one already. Fill the cache
		*	and move iterator onto next boundary. Will throw on error and not attempt to
		*	recover the iterator. Care should be taken if a string begins with an invalid
		*	character. Will also adjust cache to reflect and changes made to the iterator.
		*/
		template < typename T > void initialize ( void ) ;
		template <> void initialize< utf32 >( void )
		{
			if ( constants::isValidCodepoint( *m_Iter ) )
				m_Cache.set< _ToType >( *m_Iter );
			++m_Iter;
		}
		template <> void initialize< utf16 >( void )
		{
			if ( constants::isTrailingSurrogate( *m_Iter ) )
			{
				--m_Iter;
				m_Cache.set< _ToType >( toUtf32< _FromType >() );
				++m_Cache;
				return;
			}
			
			m_Cache.set< _ToType >( toUtf32< _FromType >() );
		}
		template <> void initialize< utf8 >( void )
		{
			if ( constants::isTrailingByte( *m_Iter ) )
			{
				difference_type nCount = 1;
				while ( constants::isTrailingByte( *(--m_Iter) ) )
					++nCount;
				m_Cache.set< _ToType >( toUtf32< _FromType >() );
				while ( nCount != 0 )
				{
					++m_Cache;
					--nCount;
				}
			}
			else
			{
				m_Cache.set< _ToType >( toUtf32< _FromType >() );
			}
		}

		/*
		*	Adjust the iterator and fill the cache.
		*/
		void initialize ( void )
		{
			if ( m_Cache.empty() )
			{
				initialize< _FromType >();
			}
		}

		/*
		*	Move the logical iter by the specified amount. decrease() will always
		*	refill the cache, but increase() will not. This is because there is no
		*	way of knowing if at end of string or not.
		*/
		iterator & increase ( difference_type _val )
		{
			// Always increase the iterator based on the converted character type.
			// If cache is empty, increase the underlying iterator.
			// Underlying iterator must always be at end of cache.
			// DO NOT - refill the cache

			while ( _val != 0 )
			{
				if ( ! m_Cache.empty() )
				{
					++m_Cache;
					--_val;
				}

				if ( m_Cache.empty() )
				{
					m_Cache.clear();

					// m_Iter is at end of cache. If also at end of string then this shouldn't have been called.
					// a call to fillCache will increase the iterator but the cache will need manually increasing.

					// For the remainder of _val, move the iterator.
					while ( _val > 0 )
					{
						fillCache();
						if ( m_Cache.length() < _val )
						{
							_val -= m_Cache.length();
							continue;
						}
						break;
					}
					for ( ; _val != 0; --_val )
						++m_Cache;
					break;
				}
			}

			return *this;
		}
		iterator & decrease ( difference_type _val )
		{
			// Always decrease the iterator based on the converted character type.
			// If cache is empty, decrease the underlying iterator.
			// Underlying iterator must always be at end of cache.
			// Cache must always be refilled

			while ( _val != 0 )
			{
				if ( m_Cache.index() == 0 )
				{
					prevCodepoint< _FromType >( m_Iter );

					// Fill the cache from the previous code point
					do {
						// An exception may be thrown here if iterating to before the start of the string.
						// Add the code point to the cache, this will give us it's converted length
						prevCodepoint< _FromType >( m_Iter );
						fillCache();
						_val -= m_Cache.length();
					} while ( static_cast< signed >( _val ) > 0 );

					// _val indicates back iterations in the cache
					while ( _val != 0 )
					{
						++_val;
						++m_Cache;
					}
				}
				else
				{
					--m_Cache;
					--_val;
				}
			}

			return *this;
		}

		/*
		*	Calculates the logical distance between two iterators.
		*/
		static difference_type difference ( const iterator & _first, const iterator & _last )
		{
			if ( _first.m_Iter > _last.m_Iter )
				throw std::invalid_argument( "Iterators are in the wrong order" );
				
			iterator Temp = _first;
			difference_type nDiff = 0;

			// First count the remainder of the cache
			nDiff += Temp.m_Cache.remainder();

			// Increase iterator until it's equal to or greater than _last
			while ( Temp.m_Iter < _last.m_Iter )
			{
//				Temp.nextCodepoint< _FromType >( Temp.m_Iter );
				Temp.fillCache();
				nDiff += Temp.m_Cache.length();
			}
			
			// Increase the cache until they are equal
			while ( Temp.m_Cache.index() < _last.m_Cache.index() )
			{
				++Temp.m_Cache;
				++nDiff;
			}

			return nDiff;
		}

	public:
		iterator ( void ) {}

		iterator ( _Iterator _iter ) : m_Iter( _iter )
		{
		}
		
		reference operator * ( void )
		{
			initialize();
			return m_Cache.get< _ToType >();
		}
		pointer operator -> ( void )
		{
			/*
			*	I don't know why string iterators have this, but for the sake of being complete...
			*/
			return (&**this);
		}
		reference operator [] ( difference_type _val ) const
		{
			return (*(*this + _val));
		}

		iterator & operator ++ ( void ) 
		{
			return increase( 1 );
		}
		iterator operator ++ ( int )
		{
			iterator Temp = *this;
			increase( 1 );
			return Temp;
		}  
		iterator & operator -- ( void )
		{
			return decrease( 1 );
		}
		iterator operator -- ( int )
		{
			iterator Temp = *this;
			decrease( 1 );
			return Temp;
		}
		iterator & operator += ( difference_type _val )
		{
			return increase( _val );
		}
		iterator & operator -= ( difference_type _val )
		{
			return decrease( _val );
		}

		iterator operator + ( difference_type _val ) const
		{
			iterator Temp = *this;
			return (Temp.increase( _val ));
		}
		iterator operator - ( difference_type _val ) const
		{
			iterator Temp = *this;
			return (Temp.decrease( _val ));
		}

		/*
		*	The following operators will result in undefined behavior if
		*	compared against an iterator not from the same container.
		*/
		difference_type operator - ( const iterator & _other ) const
		{
			return difference( _other, *this );
		}

		bool operator == ( const iterator & _other ) const 
		{
			return (m_Iter == _other.m_Iter && m_Cache == _other.m_Cache);
		}
		bool operator != ( const iterator& _other ) const
		{
			return ! (*this == _other);
		}

		bool operator < ( const iterator & _other ) const
		{
			return ( m_Iter < _other.m_Iter || (m_Iter == _other.m_Iter && m_Cache.index() < _other.m_Cache.index()) );
		}
		bool operator > ( const iterator & _other ) const
		{
			return (_other < *this);
		}
		bool operator <= ( const iterator & _other ) const
		{
			return (!(_other < *this));
		}
		bool operator >= ( const iterator & _other ) const
		{
			return (!(*this < _other));
		}
	};
}